package cn.rocky.structures.hash_table;

/**
 * 1.开放寻址等设计会对碰撞的元素寻找哈希桶上新的位置,这个位置从当前碰撞位置开始向后寻找,直到找到空的位置存放
 * 2.在ThreadLocal的实现中会使用斐波拉契、索引计算累加、启发式清理、探测式清理等操作,以保证尽可能少的碰撞。
 */
public class HashMap03ByOpenAddressing<K, V> implements Map<K, V> {

    private final Node<K, V>[] tab = new Node[8];

    //    @Override
//    public void put(K key, V value) {
//        int idx = key.hashCode() & (tab.length - 1);
//        if (tab[idx] == null) {
//            tab[idx] = new Node<>(key, value);
//        } else {
//            for (int i = idx; i < tab.length; i++) {
//                if (tab[i] == null) {
//                    tab[i] = new Node<>(key, value);
//                    break;
//                }
//            }
//        }
//    }
//
//    @Override
//    public V get(K key) {
//        int idx = key.hashCode() & (tab.length - 1);
//        for (int i = idx; i < tab.length; i++) {
//            if (tab[idx] != null && tab[idx].key == key) {
//                return tab[idx].value;
//            }
//        }
//        return null;
//    }
    @Override
    public void put(K key, V value) {
        int idx = key.hashCode() & (tab.length - 1);
        if (tab[idx] == null) {
            tab[idx] = new Node<>(key, value);
        } else {
            for (int i = idx; i < tab.length; i++) {
                if (tab[i] == null) {
                    tab[i] = new Node<>(key, value);
                    break;
                }
            }
        }
    }

    @Override
    public V get(K key) {
        int idx = key.hashCode() & (tab.length - 1);
        for (int i = idx; i < tab.length; i++) {
            if (tab[idx] != null && tab[idx].key == key) {
                return tab[idx].value;
            }
        }
        return null;
    }

    static class Node<K, V> {
        final K key;
        V value;

        public Node(K key, V value) {
            this.key = key;
            this.value = value;
        }

    }

    @Override
    public String toString() {
        StringBuilder stringBuilder = new StringBuilder();
        for (int i = 0; i < tab.length; i++) {
            if (tab[i] == null || tab[i].key == null) {
                continue;
            }
            stringBuilder.append("第").append(i).append("个元素,Key:").append(tab[i].key).append(",value:").append(tab[i].value).append("\n");
        }
        return stringBuilder.toString();
    }

    public static void main(String[] args) {
        Map<String, String> map = new HashMap03ByOpenAddressing<>();
        map.put("01", "花花");
        map.put("05", "豆豆");
        System.out.println("碰撞前 key：" + "01" + " value：" + map.get("01"));

        // 下标碰撞
        map.put("09", "蛋蛋");
        map.put("12", "苗苗");
        System.out.println("碰撞前 key：01 value：" + map.get("01"));
        System.out.println("碰撞前 key：09 value：" + map.get("09"));

        System.out.println("09".hashCode() & 7);
        System.out.println("01".hashCode() & 7);
        System.out.println(map);
    }
}
